//剑指 Offer 57. 和为s的两个数字
//思路：利用升序的规律，将时间复杂度控制在 O(N)
//1.使用头尾双指针，将首尾两个位置的元素相加与target比较
//2.以不等于作为循环条件，不等于分两种情况：1> 小于target，让 i++；
//										 2> 大于target，让 j--。

#include <stdio.h>
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int begin = 0, end = numsSize - 1;
    int sum = nums[begin] + nums[end];

    while (sum != target)//不等于
    {
        if (sum < target)//小于
            begin++;
        else//大于
            end--;
        //重置sum
        sum = nums[begin] + nums[end];
    }

    int* ret = (int*)malloc(sizeof(int) * 2);
    if (ret == NULL)
        return NULL;
    *returnSize = 2;
    //将两个值放入ret
    ret[0] = nums[begin];
    ret[1] = nums[end];
    return ret;
}